package com.wkr.demo;

import java.util.Arrays;

public class Main {

    public static int xx = 1;


    static {
        xx = 2;
        System.out.println(10);
    }

    @How(value = "how")
    public static void main(String[] args) throws ClassNotFoundException, NoSuchMethodException {
//        int[] arr = {8, 5, 3, 1, 2, 4, 9};
//        insertSort(arr);
//        System.out.println(Arrays.toString(arr));
        //   Class.forName("com.wkr.demo.How");

//        Method method = Main.class.getMethod("main", String[].class);
//        How how = method.getAnnotation(How.class);
//        System.out.println(how.value());
//        int[] a = {3, 3, 4, 4, 4, 5, 6, 6, 6, 7, 8, 8, 12, 13, 15, 16, 21, 21, 22, 24, 24, 27, 28, 32, 34, 35, 35, 36, 36, 39, 40, 41, 41, 42, 44, 44, 45, 45, 47, 47, 47, 47, 48, 48, 50, 51, 51, 53, 53, 53, 54, 54, 54, 56, 56, 57, 59, 60, 60, 60, 60, 61, 62, 63, 65, 65, 65, 65, 67, 67, 68, 70, 71, 71, 74, 75, 75, 79, 81, 84, 84, 86, 86, 87, 90, 90, 90, 90, 91, 92, 93, 94, 94, 94, 95, 97, 97, 98, 98, 99};
//        int[] aa = {1, 2, 4, 4, 5};
//        System.out.println(upper_bound_(5, 2, aa));
        int[] a = {8, 9, 3, 6, 5, 4, 7, 2, 1};
        QKSourt(a,0,a.length-1);
    }

    /**
     * 快排
     * @param a
     * @param start
     * @param end
     */
    private static void QKSourt(int[] a, int start, int end) {
        if (a.length < 0){
            return ;
        }
        if (start >= end){
            return ;
        }
        int left = start;
        int right = end;
        int temp = a[left];
        while (left < right){
            while (left < right && a[right] >= temp){
                right -- ;
            }
            a[left] = a[right];
            while (left < right && a[left] <= temp){
                left ++ ;
            }
            a[right] = a[left];
        }
        a[left] = temp;
        System.out.println(Arrays.toString(a));
        QKSourt(a, start, left -1);
        QKSourt(a,left+1,end);
    }

    /**
     * 冒泡排序
     * 每一轮找出未排序前的最大值，交换到后面
     *
     * @param args 待排序数据
     */
    public static void bubbleSort(int[] args) {
        for (int i = 0; i < args.length; i++) {
            for (int j = 0; j < args.length - i - 1; j++) {
                if (args[j] > args[j + 1]) {
                    int temp = args[j];
                    args[j] = args[j + 1];
                    args[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 选择排序
     * 第一个开始 每一轮找出未排序前最小的数据 对比交换
     *
     * @param args 待排序数据
     */
    public static void selectionSort(int[] args) {
        for (int i = 0; i < args.length; i++) {
            int min = args[i];
            int flag = i;
            for (int j = i + 1; j < args.length; j++) {
                if (args[j] < min) {
                    min = args[j];
                    flag = j;
                }
            }
            if (i != flag) {
                int temp = args[i];
                args[i] = args[flag];
                args[flag] = temp;
            }
        }
    }

    /**
     * 插入排序
     * 每一轮 前面一个作为已排序数据 后面一个作为未排序 与前面比较 后者小则交换
     *
     * @param args 待排序数据
     */
    public static void insertSort(int[] args) {
        for (int i = 1; i < args.length; i++) {
            for (int j = i; j > 0; j--) {
                if (args[j] < args[j - 1]) {
                    int temp = args[j];
                    args[j] = args[j - 1];
                    args[j - 1] = temp;
                } else {
                    break;
                }
            }
        }
    }

    public static int upper_bound_(int n, int v, int[] a) {
        // write code here
        int left = 0;
        int right = n - 1;
        while (right >= left) {
            int mid = (left + right) / 2 + 1;
            if (a[mid] == v) {
                return mid + 1;
            } else if (a[mid] > v) {
                right = mid - 1;
            } else if (a[mid] < v) {
                left = mid + 1;
            }
        }
        return -1;
    }

}
